#include <bits/stdc++.h>
using namespace std;
void swap(vector<int>& arr, int i, int j){
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

void insertsort(vector<int>& arr){
    if(arr.size() < 2){
        return;
    }
    for(int i = 1; i < arr.size(); i++){
        for(int j = i - 1; j >= 0; j--){
            if(arr[j+1] < arr[j]){
                swap(arr, j+1, j);
            }
        }
    }
}

void bubblesort(vector<int>& arr){
    if(arr.size() < 2){
        return;
    }
    for(int end = arr.size() - 1; end > 0; end--){
        for(int j = 0; j < end; j++){
            if(arr[j] > arr[j+1]){
                swap(arr, j, j+1);
            }
        }
    }
}
void selectsort(vector<int> & arr){
    if(arr.size() < 2){
        return;
    }
    int minval = 0;
    for(int i = 0; i < arr.size() - 1; i++){
        minval = i;
        for(int j = i + 1; j < arr.size(); j++){
            if(arr[j] < arr[minval]){
                minval = j;
            }
        }
        swap(arr, i, minval);
    }
}
void printvector(vector<int>& arr){
    for(auto it : arr){
        cout << it << " ";
    }
    cout << endl;
}

void testcases(void){
    vector<vector<int>> testCases = {
        {},                // 空数组
        {1},               // 单元素
        {5, 3, 2, 4, 1},  // 乱序
        {1, 2, 3, 4, 5},  // 已排序
        {5, 4, 3, 2, 1}   // 逆序
    };
    for (auto& arr : testCases) {
        cout << "排序前: ";
        printvector(arr);
        bubblesort(arr);
        cout << "排序后: ";
        printvector(arr);
        cout << "------------------" << endl;
    }
}


int main(int argc, char** argv){
    testcases();
    return 0;
}